1.47

题目

Let $Σ = {1, #}$ and let

Y = {w ∣ w = x_{1} # x_{2} # \dots # x_{k} for k \geq 0, each x_{i} \in 1^{*}, and x_{i} \neq x_{j} for i \neq j} .

Prove that $Y$ is not regular.

思路

点击展开

考虑使用泵引理，将 $x_{1}$ 泵成 $x_{i}, i > 1$

解答

点击展开

使用泵引理，设 pumping length $= p$ , 构造 $ω = 1^{p} # 1^{p - 1} # . . . # 11 # 1 #$ , 采用 pump down 方法，将 y 泵为 $ε$ , 从而将 $x_{1}$ 中 $1$ 的数量减少，与 $x_{i}, i > 1$ 重合